In order for a router to participate in a routing protocol with one or more neighbouring nodes, the router must be capable of responding to messages received from those neighbouring nodes. Depending on the type of received message, different types of tasks will be scheduled for execution by a central processing unit (CPU) within the router. For instance, some messages will require a timely response to the sender in order to show that the router is functioning properly. Other received messages, such as network topology updates, do not require a speedy response to be issued but instead may require a large background processing job to be initiated by the CPU.
If the router is currently in the process of receiving a message of the former type, i.e., requiring a timely response, but the CPU is busy handling a previously received message that has initiated a lengthy background processing job, then the router will temporarily be unable to respond to the currently received message. Under such circumstances, tasks associated with responding to the currently received message will be added to a set of tasks (e.g., in the form of a list) that shall be performed by the CPU as soon as it is free to do so. As tasks are completed, they are removed from the set of tasks or otherwise marked as complete.
Consequently, the set of incomplete tasks grows and shrinks dynamically, depending on the rate of arrival of new messages and also depending on the rate at which previously received messages can be processed by the CPU. Whether the router can respond in a timely fashion to all time-critical messages that may be received is a function of several factors, including the number of tasks in the task set, the average number of CPU cycles needed to execute a task in the task set and the processing power of the CPU itself.
Typically, the average number of CPU cycles per task is determined by the routing protocol being run by the router, while the processing speed of the CPU is bounded above by the state of CPU technology at the time the router was designed or manufactured. Hence, for a given routing protocol and a given CPU processing speed, the responsiveness of a router will depend chiefly on the number of tasks in the task set, which is a function of the rate at which received messages are received. Since the rate of received messages is a function of the number of neighbour nodes with which the router may exchange information via a set of communication ports, it follows that the ability of a router to respond in a timely fashion to received messages is proportional to the number of communication ports in use.
In conventional routers, for a given routing protocol (such as OSPF, for example), the CPU is sufficiently fast and the number of ports sufficiently low (e.g., 8 to 16) to allow the router to respond to most received messages in a timely fashion. However, a significant increase in the number of ports (e.g., to several thousand or more) would result in a severe drop in responsiveness of conventional routers given their present-day design. This would lead to a greater proportion of time-critical messages not being responded to within a maximum acceptable delay, which would cause neighbouring nodes to assume that the router is not alive. This, in turn, would cause the emission of even more messages by the neighbouring nodes, which would not only cause more tasks to be added to the ever-growing task set, but would consume valuable network bandwidth as well.
Clearly, it would be advantageous to provide a router with the capability of responding to time-critical messages as the router is scaled to a large number of ports, without having to redesign the routing protocol or wait for future advances in CPU performance.